Program compilation is comprised of a number of steps one of which is register allocation for variables in the program. One popular allocation method uses graph coloring and was first described by Chaitin, e.g. in U.S. Pat. No. 4,571,678 that is incorporated by reference herein in its entirety. See also an article entitled “Register Allocation Via Coloring” by G. J. Chaitin et al. appearing in Computer Languages, Vol. 6, pages 47–57, Pergamon Press, Great Britain, 1981 that is incorporated by reference herein in its entirety.
Chaitin's allocator assumes that the software program can use an unlimited number of registers (also called “virtual registers”), constructs an interference graph that models conflicts between virtual registers. The vertices of the interference graph represent virtual registers, and edges connect virtual registers that cannot be assigned to the same real register.
After interference graph has been built, the interference graph's nodes are ordered, and then for each node in this order, a color is chosen from a list of k colors, where k represents the number of real registers in the computer. Each node is colored with a color different from the color of any node to which it is connected (also called “neighbor”). If such a k-coloring cannot be found, one or more values (in virtual registers) are spilled to memory, and the allocator repeats the entire process (but with spilled registers removed from among the virtual registers to be allocated).
In the case of irregular hardware architecture, where irregularity is in the fact that there are registers in which the most significant part and the least significant part can be referenced as separate hardware resources, Chaitin's allocator overspills e.g. spills virtual registers even in cases where real registers are available in the computer. Such overspillage may be reduced by adding extra edges or extra nodes. Use of extra edges is described by Preston Briggs, Keith D. Cooper and Linda Torczon in an article entitled “Coloring Register Pairs”, ACM Letters on Programming Languages and Systems, 1(1):3–13, March 1992 that is incorporated by reference herein in its entirety. Use of extra nodes is described by B. Nickerson in an article entitled “Graph Coloring Register Allocation for Processors with Multi-Register Operands,” Proc. SIGPLAN′90, Conf. on Programming Language Design and Implementation, pp 40–52, June 1990.
However, use of extra edges and/or extra nodes increases the complexity of the interference graph. Instead, weights may be assigned to nodes in the interference graph as stated by Michael D. Smith and Glenn Holloway in an article entitled “Graph-Coloring Register Allocation for Architectures with Irregular Register Resources.” This article is believed to have been submitted for publication to the ACM SIGPLAN 2002 Conference on Programming Language Design and Implementation, June 2002, and is incorporated by reference herein in its entirety.
FIGS. 1A and 1B illustrate the register allocator's view of general purpose register resources that are available in the well known x86 instruction set architecture. A resource array having 10 elements is used for the x86 general purpose register file. This resource array is shown in FIG. 1A by a bit vector 101. Each square of the array represents an allocable register resource. The shaded squares in FIG. 1A indicate resources consumed by a particular register name.
As shown in FIG. 1A, register AX consumes the same resources as the two individual registers AL and AH. Specifically, the first two elements of the bit vector (collectively labeled as 112 in FIG. 1A) that are consumed by register AX are same as two elements that are individually consumed by registers AL and AH (labeled as 111A and 111B). Moreover, register EAX is represented by these same two elements of the bit vector (which are labeled as 113), because the upper half of EAX is inaccessible.
Bit vector 101 forms a component of a register class data structure that is used by the register allocator. The register class data structure includes, in addition to bit vector 101, a resource mask 121 (to indicate which hardware resources are available to candidates of a class), weights 122, placements 123, and the following lists of register names:
Ca: {AX, EAX, BX, EBX, CX, ECX, DX, EDX}
Cb: {AL, AH, BL, BH, CL, CH, DL, DH}
Ci: {DI, EDI, SI, ESI}
Cm: {AX, EAX, BX, EBX, CX, ECX, DX, EDX, DI, EDI, SI, ESI}
Class Ca represents the 16- and 32 bit variants of the A, B, C and D registers, and Class Cb represents the nameable 8 bit portions of these registers; class Ci represents 16 bit and 32 bit variants of Di and Si; and Class Cm is a multi-bank register class comprising candidates from Ca and Ci. Class Ci is assigned to all weighted interference graph (WIG) nodes representing registers DI and SI, and class Cm is used for all other 16/32 bit candidates.
The above name lists are used when allocating colors. When a candidate ‘n’ is popped from the stack, the register allocator visits each neighbor of n in the WIG and builds a list of used (unavailable)(colors. The register allocator determines the resources used by each neighbor by use of bit vector 101. It then intersects a vector of unavailable colors against the hardware resources used by each of the register names in n's class. If the intersection is the empty bit vector, that register name is an available color for n. In the case of registers AX and EAX, the actual register name returned is the one whose bit size matches the bit size of the register candidate.